package Leetcode第二期;

import java.util.Stack;

/**
 * @author : K k
 * @date : 11:07 2020/9/20
 * 在一个「平衡字符串」中，'L' 和 'R' 字符的数量是相同的。
 *
 * 给出一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。
 *
 * 返回可以通过分割得到的平衡字符串的最大数量。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：s = "RLRRLLRLRL"
 * 输出：4
 * 解释：s 可以分割为 "RL", "RRLL", "RL", "RL", 每个子字符串中都包含相同数量的 'L' 和 'R'。
 * 示例 2：
 *
 * 输入：s = "RLLLLRRRLR"
 * 输出：3
 * 解释：s 可以分割为 "RL", "LLLRRR", "LR", 每个子字符串中都包含相同数量的 'L' 和 'R'。
 */
public class 分割平衡字符串_1221 {

    //栈
    public int balancedStringSplit(String s) {
        Stack<Character> stack=new Stack<>();

        if(s==null || s.length()==0 ||s.length()==1) {return 0;}
        stack.push(s.charAt(0));
        int count=0;
        for(int i=1;i<s.length();i++){
            if (!stack.isEmpty()){
                if (stack.peek()!=s.charAt(i)){
                    stack.pop();
                    if (stack.size()==0){
                        count++;
                    }
                }else {
                    stack.push(s.charAt(i));
                }
            }else {
                stack.push(s.charAt(i));
            }
        }
        return count;
    }

    //贪心
    public int balancedStringSplitB(String s) {
        int num = 0;
        int res = 0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i) == 'L')
                {num++;}
            else
                {num--;}
            if(num == 0)
                {res++;}
        }
        return res;
    }


        public static void main(String[] args) {
        分割平衡字符串_1221 x=new 分割平衡字符串_1221();
        System.out.println(x.balancedStringSplitB("RLLLLRRRLR"));
    }
}

